package com.cuz.daileetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * @author cuzz
 * @version 1.0
 * @description: 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 * 提示：
 * <p>
 * 1 <= n <= 8
 * @date 20:07 2021/10/4
 **/

public class Day16 {
    static class S1 {
        public static void main(String[] args) {
            System.out.println(new S1().generateParenthesis(3));
        }

        public List<String> generateParenthesis(int n) {
            List<String> res = new LinkedList<>();
            backTrack(res, new StringBuilder(), n, n, n);
            return res;
        }

        /**
         * n n
         * (
         * n-1 n
         * ((  ()
         */
        private void backTrack(List<String> res, StringBuilder temp, int leftParenthesis, int rightParenthesis, int max) {
            if (leftParenthesis == 0 && rightParenthesis == 0) {
                res.add(temp.toString());
                return;
            }
            if (leftParenthesis > 0) {
                temp.append('(');
                backTrack(res, temp, leftParenthesis-1, rightParenthesis, max);
                temp.deleteCharAt(temp.length() - 1);
            }
            if (rightParenthesis > 0 && rightParenthesis > leftParenthesis) {
                temp.append(')');
                backTrack(res, temp, leftParenthesis, rightParenthesis-1, max);
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }
}
